package com.arron.algorithm.leetcodetop100.二叉树;

import com.arron.algorithm.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 *
 * 106. 从中序与后序遍历序列构造二叉树
 *
 *
 */
public class BuildTree {





    HashMap<Integer,Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {


        for (int i = 0; i < inorder.length;i++) {

            map.put(inorder[i],i);

        }

        TreeNode root= buildTree(inorder,0,inorder.length-1
                ,postorder,0,postorder.length-1);

        return root;

    }

    public TreeNode buildTree02(int[] inorder,int inorderStart,int  inorderEnd, int[] postorder,int postorderStart,int  postorderEnd){

        if (inorderStart > inorderEnd ||postorderStart > postorderEnd){
            return null;
        }

        int midIndex = map.get(postorder[postorderEnd]);


        TreeNode treeNode = new TreeNode(postorder[postorderEnd]);
        int leftsize = midIndex-inorderStart;
        treeNode.left = buildTree(inorder,inorderStart,midIndex-1,postorder,postorderStart,postorderStart+leftsize-1);
        treeNode.right = buildTree(inorder,midIndex+1,inorderEnd,postorder,postorderStart+leftsize,postorderEnd-1);

        return treeNode;
    }


    public TreeNode buildTree(int[] inorder,int inorderStart,int  inorderEnd, int[] postorder,int postorderStart,int  postorderEnd){

        if (inorderStart > inorderEnd ||postorderStart > postorderEnd){
            return null;
        }

        int midIndex = map.get(inorder[inorderStart]);


        TreeNode treeNode = new TreeNode(inorder[inorderStart]);

        treeNode.left = buildTree(inorder,inorderStart+1,inorderStart+midIndex-postorderStart,postorder,postorderStart,midIndex-1);
        treeNode.right = buildTree(inorder,inorderStart+midIndex-postorderStart+1,inorderEnd,postorder,midIndex+1,postorderEnd);

        return treeNode;
    }





    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();

        // 构建二叉树:       1
        //                / \
        //               2   3
        //              / \
        //             4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        int[] inorder={1,2,4,5,3};
        int[] postorder ={4,2,5,1,3};
        TreeNode treeNode = buildTree.buildTree(inorder, postorder);
        System.out.println(treeNode);
    }


    // 构建二叉树:       1
    //                / \
    //               2   3
    //              / \
    //             4   5
    public TreeNode buildTree(){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        return root;
    }




}
